class Solution {
    /**
     * bfs注意要在加入队列的同时标记，不然会重复入队：
     * 
     *  visit[x][y] = 1;         
     *  q.add(new Pair<>(x, y));
     */
    int[][] visit;
    int[][] nex = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int row, col;

    public int maxAreaOfIsland(int[][] grid) {
        row = grid.length;
        if (row > 0) {
            col = grid[0].length;
        } else {
            return 0;
        }
        visit = new int[row][col];
        int ans = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1 && visit[i][j] == 0) {
                    ans = Math.max(ans, bfs(grid, i, j));
                }
            }
        }
        return ans;
    }

    public int bfs(int[][] grid, int i, int j) {
        int ans = 0;
        Queue<Pair<Integer, Integer>> q = new LinkedList<>();
        q.add(new Pair<>(i, j));
        visit[i][j] = 1;
        while (q.size() > 0) {
            Pair<Integer, Integer> tot = q.poll();

            ans++;
            for (int k = 0; k < 4; k++) {
                int x = tot.getKey() + nex[k][0];
                int y = tot.getValue() + nex[k][1];
                if (x < 0 || x >= row || y < 0 || y >= col)
                    continue;
                if (grid[x][y] == 0 || visit[x][y] == 1)
                    continue;

                visit[x][y] = 1;          // ！！必须在加入队列的时候标记
                q.add(new Pair<>(x, y));
            }
        }
        return ans;
    }
}